package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import astudy.util.AdvMath;
import astudy.util.Combination;

public class Problem051 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Integer[] ps = AdvMath.primes(10000000);
		for (int i = 0; i < ps.length; i ++) {
			if (check(8, ps[i], ps)) {
				return;
			}
		}
	}
	
	public static boolean check(int k, Integer p, Integer[] ps) {
		String sp = String.valueOf(p); 
		int m = sp.length();
		for (int n = 1; n <= m; n ++) {
			if (check(n,k,p,ps)) {
				return true;
			}
		}
		return false;
	}

	public static boolean check(int n, int k, Integer p, Integer[] ps) {
		
		if (n < 1) {
			return false;
		} else {
			String sp = String.valueOf(p); 
			int m = sp.length();
			if (m < n) {
				return false;
			} else {
				int[] c = new int[n];
				for (int i = 0; i < c.length; i ++) c[i] = i;
				while (c != null) {
					//check c
					char[] t = sp.toCharArray();
					List<Integer> pp = new ArrayList<Integer>();
					for (int l = 0; l < 10; l ++) {
						for (int i = 0; i < c.length;  i ++) {
							t[c[i]] = (char)('0' + l);
						}
						if (t[0] == '0') {
							continue;
						} else {
							int np = 0;
							for (int i = 0; i < t.length; i ++) {
								np *= 10;
								np += t[i]-'0';
							}
							if (Arrays.binarySearch(ps, np) > -1) {
								pp.add(np);
							}
						}
					}
					if (pp.size() >= k) {
						System.out.println(pp);
						return true;
					}
					
					c = Combination.next(m, c);
				}
			}
		}
		return false;
	}
}